package heap_1101;
// 使用小堆来维护
// size >= 0
// array != null
// array + size 满足小堆的性质
// 堆的定义：要求每个位置都比它的两个孩子（如果存在的话）要小
public class MyPriorityQueue {
    // 元素类型使用 long 类型
    // 暂时不考虑扩容的情况
    private final long[] array = new long[1000];
    private int size;       // 元素的个数

    public MyPriorityQueue(){
        size=0;
    }
    // 查看优先级队列中最小值
    // O(1)
    public long peek() {
        if (size <= 0) {
            throw new RuntimeException("空的");
        }

        return array[0];    // 根的位置就是最小值
    }
    // 把 e 添加到堆中（优先级队列）
    // 同时维护好最小堆的性质
    // 最坏情况：从叶子 -> 根
    // O(log(n))
    public void offer(long e) {
       array[size]=e;
       size++;

       int child=size-1;//新加入元素的下标
       while(child!=0){// child == 0 说明是根，不需要调整了
           int parent=(child-1)/2;//新加入元素父亲结点的下标

           if(array[parent]<=array[child]){
                break;
            }
           //交换
            long tmp=array[parent];
            array[parent]=array[child];
            array[child]=tmp;
           //向上调整
            child=parent;
        }

    }
    // 删除堆顶元素
    // 同时维护好最小堆的性质
    // O(log(n))
    public long poll() {
        if (size <= 0) {
            throw new RuntimeException("空的");
        }

        long e = array[0];

        array[0] = array[size - 1];
        array[size - 1] = 0;    // 没有意义，可以不需要这一步
        size--;//调整堆的大小
        //对根结点进行向下调整
        int parent=0;    // O(log(n))
        int child=2*parent+1;
        while(child<size){
            if(child+1<size&&array[child+1]<array[child]){
                child+=1;
            }
            if(array[child]>=array[parent]){
                break;
            }
            long tmp=array[parent];
            array[parent]=array[child];
            array[child]=tmp;

            parent=child;
            child=2*parent+1;
        }

        return e;//返回删除的元素
    }
    public static void main(String[] args) {
        MyPriorityQueuePrimitiveType q = new MyPriorityQueuePrimitiveType();

        q.offer(3);
        q.offer(9);
        q.offer(7);
        q.offer(2);
        q.offer(6);
        q.offer(8);
        q.offer(5);
        q.offer(4);
        q.offer(3);

        System.out.println(q.poll());   // 2
        q.offer(1);
        System.out.println(q.poll());   // 1
        q.offer(1);
        q.offer(0);
        System.out.println(q.poll());   // 0
        System.out.println(q.poll());   // 1
    }
}
